import java.util.*;
// 定义单个节点的类
class OneNode {
    int data; // 节点的数据域
    OneNode next; // 指向下一个节点的引用
    // 构造函数，用于初始化节点的数据域
    public OneNode(int data) {
        this.data = data;
        this.next = null;
    }
}
// 定义循环链表的类
class OneCycle {
    OneNode head; // 链表的头节点
    int length; // 链表的长度

    // 构造函数，用于初始化循环链表
    public OneCycle() {
        this.head = null;
        this.length = 0;
    }
    // 头插法插入节点
    public void headInsert(int data) {
        OneNode newNode = new OneNode(data); // 创建新节点
        if (head == null) { // 如果链表为空
            head = newNode; // 新节点成为头节点
            newNode.next = head; // 新节点的next指向自己，形成循环
        } else {
            newNode.next = head; // 新节点的next指向原头节点
            OneNode lastNode = head;
            // 找到链表的最后一个节点，使其next指向新节点
            while (lastNode.next != head) {
                lastNode = lastNode.next;
            }
            lastNode.next = newNode;
            head = newNode; // 更新头节点为新节点
        }
        length++; // 链表长度加1
    }
    // 尾插法插入节点
    public void tailInsert(int data) {
        OneNode newNode = new OneNode(data); // 创建新节点
        if (head == null) { // 如果链表为空
            head = newNode; // 新节点成为头节点
            newNode.next = head; // 新节点的next指向自己，形成循环
        } else {
            OneNode lastNode = head;
            // 找到链表的最后一个节点
            while (lastNode.next != head) {
                lastNode = lastNode.next;
            }
            lastNode.next = newNode; // 最后一个节点的next指向新节点
            newNode.next = head; // 新节点的next指向头节点，形成循环
        }
        length++; // 链表长度加1
    }
    // 删除指定值的节点
    public boolean deleteNode(int data) {
        if (head == null) { // 如果链表为空
            return false; // 删除失败
        }
        if (head.data == data) { // 如果头节点是要删除的节点
            if (head.next == head) { // 如果链表只有一个节点
                head = null; // 头节点置为null，链表为空
            } else {
                OneNode lastNode = head;
                // 找到链表的最后一个节点
                while (lastNode.next != head) {
                    lastNode = lastNode.next;
                }
                head = head.next; // 更新头节点为原头节点的下一个节点
                lastNode.next = head; // 最后一个节点的next指向新的头节点，形成循环
            }
            length--; // 链表长度减1
            return true; // 删除成功
        }
        OneNode prev = head; // 用于记录前一个节点
        OneNode curr = head.next; // 用于记录当前节点
        // 遍历链表，寻找要删除的节点
        while (curr != head) {
            if (curr.data == data) { // 如果找到了要删除的节点
                prev.next = curr.next; // 前一个节点的next指向当前节点的下一个节点，跳过当前节点
                length--; // 链表长度减1
                return true; // 删除成功
            }
            prev = curr; // 更新前一个节点为当前节点
            curr = curr.next; // 更新当前节点为下一个节点
        }
        return false; // 没找到要删除的节点，删除失败
    }
    // 反转循环链表
    public void reverse() {
        if (head == null || head.next == head) { // 如果链表为空或只有一个节点
            return; // 不需要反转
        }
        OneNode prev = null; // 用于记录前一个节点
        OneNode current = head; // 用于记录当前节点
        OneNode next; // 用于记录下一个节点
        OneNode newLast = head; // 记录反转后的最后一个节点（原头节点）
        // 遍历链表，反转节点的指向
        do {
            next = current.next; // 记录下一个节点
            current.next = prev; // 当前节点的next指向前一个节点
            prev = current; // 更新前一个节点为当前节点
            current = next; // 更新当前节点为下一个节点
        } while (current != head); // 循环直到回到头节点
        head = prev; // 更新头节点为原链表的最后一个节点
        newLast.next = head; // 原头节点（现最后一个节点）的next指向新的头节点，形成循环
    }
    // 打印链表
    public void print() {
        if (head == null) { // 如果链表为空
            System.out.println("空链表"); // 输出提示信息
            return;
        }
        OneNode curr = head; // 从头节点开始
        // 遍历链表并打印每个节点的数据
        do {
            System.out.print(curr.data + "，"); // 打印当前节点的数据
            curr = curr.next; // 移动到下一个节点
        } while (curr != head); // 循环直到回到头节点
        System.out.println(); // 打印换行
    }
    // 返回链表的长度
    public int length() {
        return this.length; // 返回链表长度
    }
}
// 主类，用于测试循环链表的操作
public class xunhuan {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于读取用户输入
        OneCycle list = new OneCycle(); // 创建循环链表对象
        System.out.println("请输入链表的初始节点地址（十六进制）："); // 提示用户输入初始节点地址
        String headAddress = scanner.nextLine(); // 读取用户输入的初始节点地址（十六进制）
        System.out.println("------初始化链表------"); // 输出提示信息
        System.out.println("head=" + headAddress); // 输出初始节点地址
        System.out.println("请输入要头插的节点值（以逗号分隔）："); // 提示用户输入要头插的节点值
        String[] headInsertValues = scanner.nextLine().split("，"); // 读取并分割用户输入的节点值
        for (String value : headInsertValues) { // 遍历分割后的每个值
            list.headInsert(Integer.parseInt(value)); // 将值转换为整数并头插到链表
        }
        System.out.println("------ 增加结点(头插法)------"); // 输出提示信息
        list.print(); // 打印链表
        System.out.println("length: " + list.length()); // 输出链表长度
        System.out.println("请输入要尾插的节点值（以逗号分隔）："); // 提示用户输入要尾插的节点值
        String[] tailInsertValues = scanner.nextLine().split("，"); // 读取并分割用户输入的节点值
        for (String value : tailInsertValues) { // 遍历分割后的每个值
            list.tailInsert(Integer.parseInt(value)); // 将值转换为整数并尾插到链表
        }
        System.out.println("------增加结点(尾插法)------"); // 输出提示信息
        list.print(); // 打印链表
        System.out.println("length: " + list.length()); // 输出链表长度
        System.out.println("------删除结点------"); // 输出提示信息
        // 读取并处理多个删除操作
        while (true) {
            System.out.println("输入要删除的节点值（输入exit退出并反转链表）："); // 提示用户输入要删除的节点值
            String input = scanner.nextLine(); // 读取用户输入的节点值或exit
            if (input.equals("exit")) { // 如果用户输入的是exit
                break; // 退出循环
            }
            int value;
            try {
                value = Integer.parseInt(input); // 尝试将输入转换为整数
            } catch (NumberFormatException e) {
                System.out.println("输入无效，请输入一个整数或exit。"); // 输入不是整数时的提示信息
                continue; // 继续下一次循环
            }
            System.out.println("删除数据为" + value + "的结点"); // 输出提示信息
            System.out.print("删除前: ");
            list.print(); // 打印删除前的链表
            if (list.deleteNode(value)) { // 尝试删除节点
                System.out.println("------删除成功------"); // 删除成功提示
                list.print(); // 打印删除后的链表
            } else {
                System.out.println("------删除失败------"); // 删除失败提示
                list.print(); // 打印删除前的链表
            }
            System.out.println("length: " + list.length()); // 输出链表长度
        }
        System.out.println("-----反转链表-----"); // 输出提示信息
        System.out.println("-----反转前-----"); // 输出提示信息
        list.print(); // 打印反转前的链表
        list.reverse(); // 反转链表
        System.out.println("-----反转后-----"); // 输出提示信息
        list.print(); // 打印反转后的链表
    }
}
